package com.Questions.fenzhi;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Random;

import java.util.Collections;
/**
 * 53. 最大子数组和
 * 返回具有一个最大和的子数组
 *
 * */
public class leetcode53 {
    public class Status{
        // 类似于数学归纳证明的思想
        // 通过某个区间所对应的特征
        // 两个区间合并的话 其特征值具有一定的关系
        // 即下一个区间的特征与合并为其的两个区间的特征存在一定的关系
        // 然后 当区间长度为1 的时候 四个特征都能确定
        public int lSum,rSum,mSum,iSum;
        // iSum 区间和
        // rSum 以右端点的最大子段和
        // lSum 以左端点的最大子段和
        // mSum 最大子段和
        public Status(int lSum,int rSum,int mSum,int iSum){
            this.lSum=lSum;
            this.rSum=rSum;
            this.mSum=mSum;
            this.iSum=iSum;
        }
    }// 内部类 以及其构造函数 用来表示一个区间的各种信息
    public int maxSubArray(int[] nums) {
        return getInfo(nums,0,nums.length-1).mSum;
    }

    public Status getInfo(int[] a,int l,int r){
        // 使用递归将这个现存数组进行分区间 直到其长度为1
        if(l==r){
            // 长度为1的区间 其四个特征都相等
            return new Status(a[l],a[l],a[l],a[l]);
        }
        int m=(l+r)>>1;
        Status lSub=getInfo(a,l,m);
        Status rSub=getInfo(a,m+1,r);
        // 注意 最下层递归最先调用这个合并函数
        // 在物理空间上 并没有真正的将数组进行分开 只是使用区间的特征
        // 将区间进行了相应的划分
        return pushUp(lSub,rSub);
    }

    public Status pushUp(Status l,Status r){
        // 将两个区间的代表特征合并
        int iSum=l.iSum+r.iSum;
        // 合并区间的 区间和是左右两个区间区间和的和
        int lSum=Math.max(l.lSum,l.iSum+r.lSum);
        // 以左端点的最大和 有两种情况 是左区间的最大和
        // 也可能是 左区间的区间和加上右区间的左端点最大和 取其中的较大者
        int rSum=Math.max(r.rSum,r.iSum+l.rSum);
        // 同理 右端点的最大和 有两种情况 是右区间右端点最大和
        // 也可能是 右区间的区间和加上左区间的右端点和
        int mSum=Math.max(Math.max(l.mSum,r.mSum),l.rSum+r.lSum);
        // 最大子段和 有三种情况
        // 1 左区间的最大和
        // 2 右区间的最大和
        // 3 左区间右端点和 +右区间左端点和
        return new Status(lSum,rSum,mSum,iSum);
    }

    // 时间复杂度 O(n) 相当于遍历了每个二叉树的结点
    // 一共有logn层 第i层有2^i-1 个结点 所有求和之后是线性时间复杂度


}
